// @algorithm @lc id=100336 lang=cpp
// @title hua-dong-chuang-kou-de-zui-da-zhi-lcof

#include "algm/algm.h"
#include <deque>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int> &nums, int k) {
        vector<int> ans;
        if ((int)nums.size() >= k && k >= 1) {
            deque<int> window;
            for (int i = 0; i < k; ++i) {
                while (!window.empty() && nums[i] >= nums[window.back()]) {
                    window.pop_back();
                }
                window.push_back(i);
            }
            for (int i = k; i < (int)nums.size(); ++i) {
                ans.push_back(nums[window.front()]);
                while (!window.empty() && nums[i] >= nums[window.back()]) {
                    window.pop_back();
                }
                if (!window.empty() && window.front() <= (i - k)) {
                    window.pop_front();
                }
                window.push_back(i);
            }
            ans.push_back(nums[window.front()]);
        }
        return ans;
    }
};